#include "Integer.h"
#include <algorithm>
#include <cmath>
#include <ctime>
#include <sstream>
#include <random>
#include <utility>


unsigned Integer::base = 10;
const unsigned Integer::MinBase = 2;
const unsigned Integer::MaxBase = 36;
const unsigned Integer::MulKaratsubaThreshold = 0x80;
const unsigned Integer::MulFFTThreshold = 0x1000000;
const unsigned Integer::SqrKaratsubaThreshold = 0x40;
const unsigned Integer::SqrFFTThreshold = 0x400000;
const Integer Integer::BigPrime("79228162514264337589248983041");
const Integer Integer::PrimitiveRoot(11);
const Integer Integer::InversePrimitiveRoot("64823042057125367118476440670");
const std::array<Integer, 32> Integer::ExpPrimitiveRoot = Integer::InitExpTable(true);
const std::array<Integer, 32> Integer::ExpInversePrimitiveRoot = Integer::InitExpTable(false);

Integer::Integer(): sgn(0), num() {}

Integer::Integer(const Integer&) = default;
Integer::Integer(Integer&&) = default;

Integer::Integer(const int n): sgn(std::sgn(n))
{
	if (n)
		this->num.push_back(static_cast<unsigned>(std::abs(n)));
}

Integer::Integer(const unsigned n): sgn(std::sgn(n))
{
	if (n)
		this->num.push_back(n);
}

Integer::Integer(const std::string &str)
{
	static const std::string numStr("00112233445566778899AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz");
	auto iter = str.begin();

	if (*iter == '-')
	{
		this->sgn = -1;
		++iter;
	}
	else
	{
		this->sgn = 1;

		if (*iter == '+')
			++iter;
	}

	while (*iter == '0' && iter != str.end())
		++iter;

	if (iter == str.end())
		this->sgn = 0;
	else
	{
		const unsigned long long _longbase = base;

		for (; iter != str.end(); ++iter)
		{
			unsigned b;

			for (b = 0; b < base && (*iter != numStr[2 * b] && *iter != numStr[2 * b + 1]); ++b);

			if (b == base)
				throw;

			unsigned long long temp = b;

			for (auto &x: this->num)
			{
				temp += x * _longbase;
				x = static_cast<unsigned>(temp);
				temp >>= 32;
			}

			if (temp)
				num.push_back(static_cast<unsigned>(temp));
		}
	}
}

Integer& Integer::operator=(const Integer &) = default;
Integer& Integer::operator=(Integer&&) = default;

Integer::~Integer() = default;

void Integer::SetBase(const unsigned base)
{
	if (base < MinBase || base > MaxBase)
		throw;

	Integer::base = base;
}

std::string Integer::str() const
{
	if (this->sgn == 0)
		return "0";

	std::ostringstream str;
	static const unsigned exp[37] = {0, 0, 32, 20, 16, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 8,
									 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6
									};
	unsigned long long bigbase = base;

	for (unsigned i = 1; i < exp[base]; ++i)
		bigbase *= base;

	if (this->sgn == -1)
		str << '-';

	std::vector<unsigned> digit;
	digit.reserve(static_cast<unsigned>
				  (32 * log(2.0) * this->num.size() / log(static_cast<double>(bigbase))) + 1);

	for (auto iter = this->num.rbegin(); iter != this->num.rend(); ++iter)
	{
		unsigned long long temp = *iter;

		for (auto &x: digit)
		{
			temp |= static_cast<unsigned long long>(x) << 32;
			x = static_cast<unsigned>(temp % bigbase);
			temp /= bigbase;
		}

		digit.push_back(static_cast<unsigned>(temp % bigbase));

		if (temp >= bigbase)
			digit.push_back(static_cast<unsigned>(temp / bigbase));
	}

	static const std::string numStr("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ");
	unsigned n = digit.back();
	std::string s;

	do
	{
		s.insert(s.begin(), numStr[n % base]);
		n /= base;
	}
	while (n);

	str << s;

	for (auto iter = digit.rbegin() + 1; iter != digit.rend(); ++iter)
	{
		unsigned n = *iter;
		std::string s(exp[base], 0);

		for (unsigned i = 0; i < exp[base]; ++i)
		{
			s[exp[base] - 1 - i] = numStr[n % base];
			n /= base;
		}

		str << s;
	}

	return str.str();
}

std::ostream& operator<<(std::ostream &out, const Integer &n)
{
	return out << n.str();
}

unsigned _unsigned(const Integer &n)
{
	return n.sgn ? n.num.front() : 0;
}

bool operator==(const Integer &lhs, const Integer &rhs)
{
	if (lhs.sgn != rhs.sgn)
		return false;

	if (lhs.sgn == 0)
		return true;

	if (lhs.num.size() != rhs.num.size())
		return false;

	const unsigned size = lhs.num.size();

	for (unsigned i = 0; i < size; ++i)
		if (lhs.num[i] != rhs.num[i])
			return false;

	return true;
}

bool operator!=(const Integer &lhs, const Integer &rhs)
{
	return !(lhs == rhs);
}

bool operator<(const Integer &lhs, const Integer &rhs)
{
	if (lhs.sgn < rhs.sgn)
		return true;
	else if (lhs.sgn > rhs.sgn)
		return false;

	if (lhs.sgn == 0)
		return false;

	const bool reverse = lhs.sgn < 0;

	if (lhs.num.size() < rhs.num.size())
		return !reverse;
	else if (lhs.num.size() > rhs.num.size())
		return reverse;

	const unsigned size = lhs.num.size();

	for (int i = size - 1; i >= 0; --i)
	{
		if (lhs.num[i] < rhs.num[i])
			return !reverse;
		else if (lhs.num[i] > rhs.num[i])
			return reverse;
	}

	return false;
}

bool operator<=(const Integer &lhs, const Integer &rhs)
{
	return !(rhs < lhs);
}

bool operator>(const Integer &lhs, const Integer &rhs)
{
	return rhs < lhs;
}

bool operator>=(const Integer &lhs, const Integer &rhs)
{
	return !(lhs < rhs);
}

Integer Integer::operator-() const
{
	Integer n(*this);
	n.sgn = -n.sgn;
	return std::move(n);
}

Integer operator-(Integer &&n)
{
	n.sgn = -n.sgn;
	return n;
}

bool std::IsOdd(const Integer &n)
{
	return n.Bit(0);
}

bool std::IsEven(const Integer &n)
{
	return !n.Bit(0);
}

unsigned Integer::Bits() const
{
	if (this->sgn == 0)
		return 0;

	unsigned bits = ((this->num.size() - 1) << 5) + 1;

	for (unsigned n = this->num.back() >> 1; n; n >>= 1, ++bits);

	return bits;
}

bool Integer::Bit(const unsigned bit) const
{
	if ((bit >> 5) > this->num.size())
		return false;

	return (this->num[bit >> 5] & (1 << (bit & 0x1f))) != 0;
}

Integer operator+(const Integer &lhs, const Integer &rhs)
{
	if (rhs.sgn == 0)
		return lhs;
	else if (lhs.sgn == 0)
		return rhs;

	const unsigned l1 = lhs.num.size();
	const unsigned l2 = rhs.num.size();

	if (lhs.sgn == rhs.sgn)
	{
		Integer sum;
		sum.sgn = lhs.sgn;
		unsigned long long temp = 0;

		if (l1 > l2)
		{
			sum.num.reserve(l1 + 1);

			for (unsigned i = 0; i < l2; ++i)
			{
				temp = temp + lhs.num[i] + rhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = temp > 0xffffffff;
			}

			for (unsigned i = l2; i < l1; ++i)
			{
				temp += lhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = temp > 0xffffffff;
			}
		}
		else
		{
			sum.num.reserve(l2 + 1);

			for (unsigned i = 0; i < l1; ++i)
			{
				temp = temp + lhs.num[i] + rhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = temp > 0xffffffff;
			}

			for (unsigned i = l1; i < l2; ++i)
			{
				temp += rhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = temp > 0xffffffff;
			}
		}

		if (temp)
			sum.num.push_back(1);

		return std::move(sum);
	}
	else if (lhs.num == rhs.num)
		return 0;
	else
	{
		Integer sum;
		long long temp = 0;

		if (std::abs(lhs) > std::abs(rhs))
		{
			sum.sgn = lhs.sgn;
			sum.num.reserve(l1);

			for (unsigned i = 0; i < l2; ++i)
			{
				temp = temp + lhs.num[i] - rhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = -(temp < 0);
			}

			for (unsigned i = l2; i < l1; ++i)
			{
				temp += lhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = -(temp < 0);
			}
		}
		else
		{
			sum.sgn = rhs.sgn;
			sum.num.reserve(l2);

			for (unsigned i = 0; i < l1; ++i)
			{
				temp = temp + rhs.num[i] - lhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = -(temp < 0);
			}

			for (unsigned i = l1; i < l2; ++i)
			{
				temp += rhs.num[i];
				sum.num.push_back(static_cast<unsigned>(temp));
				temp = -(temp < 0);
			}
		}

		while (!sum.num.back())
			sum.num.pop_back();

		return std::move(sum);
	}
}

Integer operator+(const Integer &lhs, Integer &&rhs)
{
	return std::move(rhs += lhs);
}

Integer operator+(Integer &&lhs, const Integer &rhs)
{
	return std::move(lhs += rhs);
}

Integer operator+(Integer &&lhs, Integer &&rhs)
{
	return std::move(lhs += rhs);
}

Integer& Integer::operator+=(const Integer &addend)
{
	if (addend.sgn == 0)
		return *this;
	else if (this->sgn == 0)
		return *this = addend;

	const unsigned l1 = this->num.size();
	const unsigned l2 = addend.num.size();

	if (this->sgn == addend.sgn)
	{
		unsigned long long temp = 0;

		if (l1 > l2)
		{
			for (unsigned i = 0; i < l2; ++i)
			{
				temp = temp + this->num[i] + addend.num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = temp > 0xffffffff;
			}

			for (unsigned i = l2; temp > 0 && i < l1; ++i)
			{
				temp += this->num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = temp > 0xffffffff;
			}
		}
		else
		{
			for (unsigned i = 0; i < l1; ++i)
			{
				temp = temp + this->num[i] + addend.num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = temp > 0xffffffff;
			}

			for (unsigned i = l1; i < l2; ++i)
			{
				temp += addend.num[i];
				this->num.push_back(static_cast<unsigned>(temp));
				temp = temp > 0xffffffff;
			}
		}

		if (temp > 0)
			this->num.push_back(1);
	}
	else if (this->num == addend.num)
		return *this = 0;
	else
	{
		long long temp = 0;

		if (std::abs(*this) > std::abs(addend))
		{
			for (unsigned i = 0; i < l2; ++i)
			{
				temp = temp + this->num[i] - addend.num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = -(temp < 0);
			}

			for (unsigned i = l2; temp < 0; ++i)
			{
				temp += this->num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = -(temp < 0);
			}
		}
		else
		{
			this->sgn = addend.sgn;

			for (unsigned i = 0; i < l1; ++i)
			{
				temp = temp + addend.num[i] - this->num[i];
				this->num[i] = static_cast<unsigned>(temp);
				temp = -(temp < 0);
			}

			for (unsigned i = l1; i < l2; ++i)
			{
				temp += addend.num[i];
				this->num.push_back(static_cast<unsigned>(temp));
				temp = -(temp < 0);
			}
		}

		while (!this->num.back())
			this->num.pop_back();
	}

	return *this;
}

Integer& Integer::operator++()
{
	return *this += 1;
}

Integer Integer::operator++(int)
{
	Integer sum(*this);
	*this += 1;
	return std::move(sum);
}

Integer operator-(const Integer &lhs, const Integer &rhs)
{
	return std::move(lhs + (-rhs));
}

Integer operator-(const Integer &lhs, Integer &&rhs)
{
	rhs += -lhs;
	rhs.sgn = -rhs.sgn;
	return std::move(rhs);
}

Integer operator-(Integer &&lhs, const Integer &rhs)
{
	return std::move(lhs += -rhs);
}

Integer operator-(Integer &&lhs, Integer &&rhs)
{
	return std::move(lhs += -rhs);
}

Integer& Integer::operator-=(const Integer &subtrahend)
{
	return *this += -subtrahend;
}

Integer& Integer::operator--()
{
	return *this += -1;
}

Integer Integer::operator--(int)
{
	Integer sum(*this);
	*this += -1;
	return std::move(sum);
}

Integer operator*(const Integer &lhs, const Integer &rhs)
{
	if (lhs.sgn == 0 || rhs.sgn == 0)
		return 0;

	const unsigned l1 = lhs.num.size();
	const unsigned l2 = rhs.num.size();

	if (std::min(l1, l2) < Integer::MulKaratsubaThreshold)
	{
		Integer product;
		product.sgn = lhs.sgn * rhs.sgn;
		product.num.resize(l1 + l2);

		for (unsigned i = 0; i < l1; ++i)
		{
			unsigned long long temp = 0;
			unsigned long long multiplier = lhs.num[i];

			for (unsigned j = 0; j < l2; ++j)
			{
				temp += multiplier * rhs.num[j] + product.num[i + j];
				product.num[i + j] = static_cast<unsigned>(temp);
				temp >>= 32;
			}

			if (temp)
				product.num[i + l2] = static_cast<unsigned>(temp);
		}

		if (!product.num.back())
			product.num.pop_back();

		return std::move(product);
	}
	else if (l1 + l2 < Integer::MulFFTThreshold)
	{
		const unsigned l = std::max(l1, l2) >> 1;
		const unsigned shift = l << 5;
		const Integer mask = Integer::Mask(l);
		const Integer a0 = lhs & mask;
		Integer a1 = lhs >> shift;
		a1.sgn = std::sgn(a1.sgn);
		const Integer b0 = rhs & mask;
		Integer b1 = rhs >> shift;
		b1.sgn = std::sgn(b1.sgn);
		const Integer c0 = a0 * b0;
		const Integer c1 = a1 * b1;
		const Integer c2 = c0 + c1 - (a0 - a1) * (b0 - b1);
		Integer product;
		product.sgn = lhs.sgn * rhs.sgn;
		product.num.reserve(l1 + l2);
		const unsigned cl = c2.num.size();

		for (const auto &x: c0.num)
			product.num.push_back(x);

		product.num.resize(l << 1);

		for (const auto &x: c1.num)
			product.num.push_back(x);

		product.num.resize(l1 + l2);

		unsigned long long temp = 0;
		unsigned i;

		for (i = 0; i < cl; ++i)
		{
			temp = temp + product.num[i + l] + c2.num[i];
			product.num[i + l] = static_cast<unsigned>(temp);
			temp = temp > 0xffffffff;
		}

		for (i += l; temp; ++i)
		{
			temp += product.num[i];
			product.num[i] = static_cast<unsigned>(temp);
			temp = temp > 0xffffffff;
		}

		if (!product.num.back())
			product.num.pop_back();

		return std::move(product);
	}
	else
	{
		unsigned length, len;

		for (length = 1, len = 0; length < l1 + l2; length <<= 1, ++len);

		std::vector<Integer> a, b, c;
		a.assign(lhs.num.begin(), lhs.num.end());
		b.assign(rhs.num.begin(), rhs.num.end());
		a.resize(length);
		b.resize(length);
		Integer::FFT(a, b);
		c.reserve(length);

		for (unsigned i = 0; i < length; ++i)
			c.push_back((a[i] * b[i]) % Integer::BigPrime);

		Integer::iFFT(c);

		while (!c.back().sgn)
			c.pop_back();

		Integer product;
		product.sgn = lhs.sgn * rhs.sgn;
		product.num.reserve(l1 + l2);
		Integer temp;
		const unsigned mask = length - 1;
		const Integer add(Integer::BigPrime >> len);

		for (const auto &x: c)
		{
			const unsigned addition = _unsigned(x) & mask;

			if (!addition)
				temp += x >> len;
			else
				temp += Integer::BigPrime - addition * add + (x >> len);

			product.num.push_back(_unsigned(temp));
			temp >>= 32;
		}

		product.num.insert(product.num.end(), temp.num.begin(), temp.num.end());
		return std::move(product);
	}
}

Integer Integer::operator*(const int factor) const
{
	if (this->sgn == 0 || factor == 1)
		return *this;
	else if (factor == 0)
		return 0;
	else if (factor == -1)
	{
		Integer product(*this);
		product.sgn = -product.sgn;
		return std::move(product);
	}

	if (factor > 0)
		return *this * static_cast<unsigned>(factor);
	else
	{
		Integer product = *this * static_cast<unsigned>(-factor);
		product.sgn = -product.sgn;
		return std::move(product);
	}
}

Integer Integer::operator*(const unsigned factor) const
{
	if (this->sgn == 0 || factor == 1)
		return *this;
	else if (factor == 0)
		return 0;

	Integer product;
	product.sgn = this->sgn;
	product.num.reserve(this->num.size() + 1);
	unsigned long long temp = 0;
	unsigned long long _longfactor = factor;
	const unsigned l = this->num.size();

	for (unsigned i = 0; i < l; ++i)
	{
		temp += this->num[i] * _longfactor;
		product.num.push_back(static_cast<unsigned>(temp));
		temp >>= 32;
	}

	if (temp)
		product.num.push_back(static_cast<unsigned>(temp));

	return std::move(product);
}

Integer operator*(const int factor, const Integer& multiplier)
{
	return multiplier * factor;
}

Integer operator*(const unsigned factor, const Integer& multiplier)
{
	return multiplier * factor;
}

Integer& Integer::operator*=(const Integer &factor)
{
	return *this = *this * factor;
}

Integer& Integer::operator*=(const int factor)
{
	if (this->sgn == 0 || factor == 1)
		return *this;
	else if (factor == 0)
		return *this = 0;
	else if (factor == -1)
	{
		this->sgn = -this->sgn;
		return *this;
	}

	if (factor > 0)
		return *this *= static_cast<unsigned>(factor);
	else
	{
		*this *= static_cast<unsigned>(-factor);
		this->sgn = -this->sgn;
		return *this;
	}
}

Integer& Integer::operator*=(const unsigned factor)
{
	if (this->sgn == 0 || factor == 1)
		return *this;
	else if (factor == 0)
		return *this = 0;

	unsigned long long temp = 0;
	unsigned long long _longfactor = factor;
	const unsigned l = this->num.size();

	for (unsigned i = 0; i < l; ++i)
	{
		temp += this->num[i] * _longfactor;
		this->num[i] = static_cast<unsigned>(temp);
		temp >>= 32;
	}

	if (temp)
		this->num.push_back(static_cast<unsigned>(temp));

	return *this;
}

Integer Square(const Integer &n)
{
	if (n == 0)
		return 0;

	const unsigned l = n.num.size();

	if (l < Integer::SqrKaratsubaThreshold)
	{
		Integer product;
		product.sgn = 1;
		product.num.resize(l << 1);

		for (unsigned i = 0; i < l; ++i)
		{
			unsigned long long temp = 0;
			unsigned long long multiplier = n.num[i];

			for (unsigned j = 0; j < l; ++j)
			{
				temp += multiplier * n.num[j] + product.num[i + j];
				product.num[i + j] = static_cast<unsigned>(temp);
				temp >>= 32;
			}

			if (temp)
				product.num[i + l] = static_cast<unsigned>(temp);
		}

		if (!product.num.back())
			product.num.pop_back();

		return std::move(product);
	}
	else if (l << 1 < Integer::SqrFFTThreshold)
	{
		const unsigned ll = l >> 1;
		const Integer a0 = n & Integer::Mask(ll);
		Integer a1 = n >> (ll << 5);
		a1.sgn = 1;
		const Integer b0 = Square(a0);
		const Integer b1 = Square(a1);
		const Integer b2 = b0 + b1 - Square(a0 - a1);
		Integer product;
		product.sgn = 1;
		product.num.reserve(l << 1);
		const unsigned bl = b2.num.size();

		for (const auto &x: b0.num)
			product.num.push_back(x);

		product.num.resize(ll << 1);

		for (const auto &x: b1.num)
			product.num.push_back(x);

		product.num.resize(l << 1);

		unsigned long long temp = 0;
		unsigned i;

		for (i = 0; i < bl; ++i)
		{
			temp = temp + product.num[i + ll] + b2.num[i];
			product.num[i + ll] = static_cast<unsigned>(temp);
			temp = temp > 0xffffffff;
		}

		i += ll;

		while (temp)
		{
			temp += product.num[i];
			product.num[i++] = static_cast<unsigned>(temp);
			temp = temp > 0xffffffff;
		}

		if (!product.num.back())
			product.num.pop_back();

		return std::move(product);
	}
	else
	{
		unsigned length, len;

		for (length = 1, len = 0; length < l << 1; length <<= 1, ++len);

		std::vector<Integer> a, b;
		a.assign(n.num.begin(), n.num.end());
		a.resize(length);
		Integer::FFT(a);
		b.reserve(length);

		for (const auto &x: a)
			b.push_back(Square(x) % Integer::BigPrime);

		Integer::iFFT(b);

		while (!b.back().sgn)
			b.pop_back();

		Integer product;
		product.sgn = 1;
		product.num.reserve(l << 1);
		Integer temp;
		const unsigned mask = length - 1;
		const Integer add = Integer::BigPrime >> len;

		for (const auto &x: b)
		{
			const unsigned addition = _unsigned(x) & mask;

			if (!addition)
				temp += x >> len;
			else
				temp += Integer::BigPrime - addition * add + (x >> len);

			product.num.push_back(_unsigned(temp));
			temp >>= 32;
		}

		product.num.insert(product.num.end(), temp.num.begin(), temp.num.end());
		return std::move(product);
	}
}

unsigned Integer::SingleLimbDivide(const Integer &divisor, Integer &remainder) const
{
	if (*this < divisor)
	{
		remainder = *this;
		return 0;
	}

	unsigned quotient;

	if (this->num.size() == divisor.num.size())
		quotient = this->num.back() / divisor.num.back();
	else
	{
		const unsigned long long q = ((static_cast<unsigned long long>(this->num.back()) << 32)
									  | (this->num[this->num.size() - 2])) / divisor.num.back();
		quotient = q >= 0xffffffff ? 0xffffffff : static_cast<unsigned>(q);
	}

	remainder = *this - divisor * quotient;

	while (remainder.sgn == -1)
	{
		quotient--;
		remainder += divisor;
	}

	return quotient;
}

Integer Divide(const Integer &dividend, const Integer &divisor, Integer &remainder)
{
	if (divisor.sgn == 0)
		throw;

	if (dividend.sgn == -1 && divisor.sgn == -1)
		return Divide(-dividend, -divisor, remainder);
	else if (dividend.sgn == -1 || divisor.sgn == -1)
	{
		Integer quotient = -Divide(std::abs(dividend), std::abs(divisor), remainder);

		if (remainder.sgn != 0)
		{
			--quotient;
			remainder = divisor - remainder;
		}

		return quotient;
	}

	if (dividend < divisor)
	{
		remainder = dividend;
		return 0;
	}

	unsigned k = 0;

	for (unsigned b0 = divisor.num.back(); b0 < 0x80000000; ++k, b0 <<= 1);

	Integer a = dividend << k;
	Integer b = divisor << k;
	unsigned l = a.num.size() - b.num.size();
	Integer quotient;
	quotient.sgn = 1;
	remainder = a >> (l << 5);

	if (remainder < b)
		quotient.num.assign(l, 0);
	else
	{
		quotient.num.assign(++l, 0);
		remainder >>= 32;
	}

	for (int i = l - 1; i >= 0; i--)
		quotient.num[i] = ((remainder << 32) | a.num[i]).SingleLimbDivide(b, remainder);

	remainder >>= k;
	return quotient;
}

Integer Divide(const Integer &dividend, const int divisor, unsigned &remainder)
{
	if (divisor == 0)
		throw;

	if (dividend.sgn == -1 && divisor < 0)
		return Divide(-dividend, static_cast<unsigned>(-divisor), remainder);
	else if (dividend.sgn == -1 || divisor < 0)
	{
		Integer quotient = -Divide(std::abs(dividend), static_cast<unsigned>(std::abs(divisor)), remainder);

		if (remainder)
		{
			--quotient;
			remainder = divisor - remainder;
		}

		return quotient;
	}
	else
		return Divide(dividend, static_cast<unsigned>(divisor), remainder);
}

Integer Divide(const Integer &dividend, const unsigned divisor, unsigned &remainder)
{
	if (divisor == 0)
		throw;

	if (dividend.sgn == -1)
	{
		Integer quotient = -Divide(-dividend, divisor, remainder);

		if (remainder)
		{
			--quotient;
			remainder = divisor - remainder;
		}

		return quotient;
	}

	if (dividend < divisor)
	{
		remainder = _unsigned(dividend);
		return 0;
	}

	unsigned l = dividend.num.size() - 1;
	Integer quotient;
	quotient.sgn = 1;
	remainder = dividend.num.back();

	if (remainder < divisor)
		quotient.num.assign(l, 0);
	else
	{
		quotient.num.assign(++l, 0);
		remainder = 0;
	}

	for (int i = l - 1; i >= 0; i--)
	{
		unsigned long long temp = (static_cast<unsigned long long>(remainder) << 32) | dividend.num[i];
		quotient.num[i] = static_cast<unsigned>(temp / divisor);
		remainder = static_cast<unsigned>(temp - static_cast<unsigned long long>(quotient.num[i]) * divisor);
	}

	return quotient;
}

Integer operator/(const Integer &lhs, const Integer &rhs)
{
	Integer remainder;
	return Divide(lhs, rhs, remainder);
}

Integer Integer::operator/(const int divisor) const
{
	unsigned remainder;
	return Divide(*this, divisor, remainder);
}

Integer Integer::operator/(const unsigned divisor) const
{
	unsigned remainder;
	return Divide(*this, divisor, remainder);
}

Integer& Integer::operator/=(const Integer &divisor)
{
	Integer remainder;
	return *this = Divide(*this, divisor, remainder);
}

Integer& Integer::operator/=(const int divisor)
{
	unsigned remainder;
	return *this = Divide(*this, divisor, remainder);
}

Integer& Integer::operator/=(const unsigned divisor)
{
	unsigned remainder;
	return *this = Divide(*this, divisor, remainder);
}

Integer operator%(const Integer &lhs, const Integer &rhs)
{
	Integer remainder;
	Divide(lhs, rhs, remainder);
	return remainder;
}

unsigned Integer::operator%(const int divisor) const
{
	unsigned remainder;
	Divide(*this, divisor, remainder);
	return remainder;
}

unsigned Integer::operator%(const unsigned divisor) const
{
	unsigned remainder;
	Divide(*this, divisor, remainder);
	return remainder;
}

Integer& Integer::operator%=(const Integer &divisor)
{
	Integer remainder;
	Divide(*this, divisor, remainder);
	return *this = std::move(remainder);
}

Integer& Integer::operator%=(const int divisor)
{
	unsigned remainder;
	Divide(*this, divisor, remainder);
	return *this = remainder;
}

Integer& Integer::operator%=(const unsigned divisor)
{
	unsigned remainder;
	Divide(*this, divisor, remainder);
	return *this = remainder;
}

Integer operator&(const Integer &lhs, const Integer &rhs)
{
	Integer n;
	unsigned l = std::min(lhs.num.size(), rhs.num.size());
	n.num.reserve(l);

	for (unsigned i = 0; i < l; ++i)
		n.num.push_back(lhs.num[i] & rhs.num[i]);

	while (!n.num.empty() && !n.num.back())
		n.num.pop_back();

	n.sgn = !n.num.empty();
	return std::move(n);
}

Integer& Integer::operator&=(const Integer &n)
{
	if (this->num.size() > n.num.size())
		this->num.resize(n.num.size());

	for (unsigned i = 0; i < this->num.size(); ++i)
		this->num[i] &= n.num[i];

	while (!this->num.empty() && !this->num.back())
		this->num.pop_back();

	this->sgn = !this->num.empty();
	return *this;
}

Integer operator|(const Integer &lhs, const Integer &rhs)
{
	if (lhs.sgn == 0)
		return std::abs(rhs);
	else if (rhs.sgn == 0)
		return std::abs(lhs);

	Integer n;
	n.sgn = 1;

	if (lhs.num.size() > rhs.num.size())
	{
		n.num.reserve(lhs.num.size());

		for (unsigned i = 0; i < rhs.num.size(); ++i)
			n.num.push_back(lhs.num[i] | rhs.num[i]);

		for (unsigned i = rhs.num.size(); i < lhs.num.size(); ++i)
			n.num.push_back(lhs.num[i]);
	}
	else
	{
		n.num.reserve(rhs.num.size());

		for (unsigned i = 0; i < lhs.num.size(); ++i)
			n.num.push_back(lhs.num[i] | rhs.num[i]);

		for (unsigned i = lhs.num.size(); i < rhs.num.size(); ++i)
			n.num.push_back(rhs.num[i]);
	}

	return std::move(n);
}

Integer& Integer::operator|=(const Integer &n)
{
	if (n.sgn == 0)
	{
		this->sgn = std::abs(this->sgn);
		return *this;
	}
	else if (this->sgn == 0)
	{
		*this = n;
		this->sgn = 1;
		return *this;
	}

	this->sgn = 1;

	if (this->num.size() > n.num.size())
	{
		for (unsigned i = 0; i < n.num.size(); ++i)
			this->num[i] |= n.num[i];
	}
	else
	{
		for (unsigned i = 0; i < this->num.size(); ++i)
			this->num[i] |= n.num[i];

		for (unsigned i = this->num.size(); i < n.num.size(); ++i)
			this->num.push_back(n.num[i]);
	}

	return *this;
}

Integer operator^(const Integer &lhs, const Integer &rhs)
{
	if (lhs.sgn == 0)
		return std::abs(rhs);
	else if (rhs.sgn == 0)
		return std::abs(lhs);

	Integer n;

	if (lhs.num.size() > rhs.num.size())
	{
		n.num.reserve(lhs.num.size());

		for (unsigned i = 0; i < rhs.num.size(); ++i)
			n.num.push_back(lhs.num[i] ^ rhs.num[i]);

		for (unsigned i = rhs.num.size(); i < lhs.num.size(); ++i)
			n.num.push_back(lhs.num[i]);
	}
	else if (lhs.num.size() < rhs.num.size())
	{
		n.num.reserve(rhs.num.size());

		for (unsigned i = 0; i < lhs.num.size(); ++i)
			n.num.push_back(lhs.num[i] ^ rhs.num[i]);

		for (unsigned i = lhs.num.size(); i < rhs.num.size(); ++i)
			n.num.push_back(rhs.num[i]);
	}
	else
	{
		for (unsigned i = 0; i < lhs.num.size(); ++i)
			n.num.push_back(lhs.num[i] ^ rhs.num[i]);

		while (!n.num.empty() && !n.num.back())
			n.num.pop_back();
	}

	n.sgn = !n.num.empty();
	return std::move(n);
}

Integer& Integer::operator^=(const Integer &n)
{
	if (n.sgn == 0)
	{
		this->sgn = std::abs(this->sgn);
		return *this;
	}
	else if (this->sgn == 0)
	{
		*this = n;
		this->sgn = 1;
		return *this;
	}

	if (this->num.size() > n.num.size())
	{
		for (unsigned i = 0; i < n.num.size(); ++i)
			this->num[i] ^= n.num[i];
	}
	else if (this->num.size() < n.num.size())
	{
		for (unsigned i = 0; i < this->num.size(); ++i)
			this->num[i] ^= n.num[i];

		for (unsigned i = this->num.size(); i < n.num.size(); ++i)
			this->num.push_back(n.num[i]);
	}
	else
	{
		for (unsigned i = 0; i < n.num.size(); ++i)
			this->num[i] ^= n.num[i];

		while (!this->num.empty() && !this->num.back())
			this->num.pop_back();

		this->sgn = !this->num.empty();
	}

	return *this;
}

Integer Integer::operator<<(const int n) const
{
	Integer m(*this);

	if (n < 0)
		return m >>= static_cast<unsigned>(-n);
	else
		return m <<= static_cast<unsigned>(n);
}

Integer Integer::operator<<(const unsigned n) const
{
	if (this->sgn == 0 || !n)
		return *this;

	Integer m;
	m.sgn = this->sgn;
	m.num.reserve(this->num.size() + (n >> 5) + 1);
	m.num.assign(n >> 5, 0);
	const unsigned n0 = n & 0x1f;

	if (!n0)
		m.num.insert(m.num.end(), this->num.begin(), this->num.end());
	else
	{
		unsigned temp = 0;

		for (const auto &x: this->num)
		{
			m.num.push_back((x << n0) | temp);
			temp = x >> (32 - n0);
		}

		if (temp)
			m.num.push_back(temp);
	}

	return std::move(m);
}

Integer& Integer::operator<<=(const int n)
{
	if (n < 0)
		return *this >>= static_cast<unsigned>(-n);
	else
		return *this <<= static_cast<unsigned>(n);
}

Integer& Integer::operator<<=(const unsigned n)
{
	if (this->sgn == 0 || n == 0)
		return *this;

	const unsigned n0 = n & 0x1f;

	if (n0)
	{
		unsigned temp = 0;

		for (auto &x: this->num)
		{
			unsigned temp2 = x >> (32 - n0);
			x = (x << n0) | temp;
			temp = temp2;
		}

		if (temp)
			this->num.push_back(temp);
	}

	this->num.insert(this->num.begin(), n >> 5, 0);
	return *this;
}

Integer Integer::operator>>(const int n) const
{
	Integer m(*this);

	if (n < 0)
		return m <<= static_cast<unsigned>(-n);
	else
		return m >>= static_cast<unsigned>(n);
}

Integer Integer::operator>>(const unsigned n) const
{
	if (this->Bits() <= n)
		return 0;

	if (n == 0)
		return *this;

	const unsigned n0 = n & 0x1f;
	Integer m;
	m.sgn = this->sgn;

	if (!n0)
		m.num.assign(this->num.begin() + (n >> 5), this->num.end());
	else
	{
		m.num.reserve(this->num.size() - (n >> 5));
		auto iter = this->num.begin() + (n >> 5);
		const auto end = this->num.end();
		unsigned temp = *iter >> n0;

		while (++iter != end)
		{
			m.num.push_back((*iter << (32 - n0)) | temp);
			temp = *iter >> n0;
		}

		if (temp)
			m.num.push_back(temp);
	}

	return std::move(m);
}

Integer& Integer::operator>>=(const int n)
{
	if (n < 0)
		return *this <<= static_cast<unsigned>(-n);
	else
		return *this >>= static_cast<unsigned>(n);
}

Integer& Integer::operator>>=(const unsigned n)
{
	if (this->Bits() <= n)
		return *this = 0;

	if (n == 0)
		return *this;

	unsigned k = n >> 5;
	const unsigned n0 = n & 0x1f;

	if (!n0)
		this->num.erase(this->num.begin(), this->num.begin() + k);
	else
	{
		unsigned temp = this->num[k] >> n0;

		while (++k < this->num.size())
		{
			this->num[k - 1 - (n >> 5)] = (this->num[k] << (32 - n0)) | temp;
			temp = this->num[k] >> n0;
		}

		if (temp)
		{
			this->num[this->num.size() - 1 - (n >> 5)] = temp;
			this->num.resize(this->num.size() - (n >> 5));
		}
		else
			this->num.resize(this->num.size() - 1 - (n >> 5));
	}

	return *this;
}

Integer Integer::Mask(const unsigned n)
{
	if (n == 0)
		return 0;

	Integer m;
	m.sgn = 1;
	m.num.assign(n, 0xffffffff);
	return std::move(m);
}

Integer IntegerRoot(const Integer &n, const unsigned root)
{
	if (root == 0)
		throw;
	else if (root == 1)
		return n;

	if (n.sgn == 0)
		return 0;
	else if (n.sgn == -1)
	{
		if (std::IsEven(root))
			throw;
		else
			return -IntegerRoot(-n, root);
	}

	Integer x;
	Integer y = 1 << ((n.Bits() + 1) / root);
	const Integer rootn(root);

	do
	{
		std::swap(x, y);
		y = (x * (root - 1) + n / std::Exp(x, root - 1)) / rootn;
	}
	while (y < x);

	return std::move(x);
}

Integer Integer::ModBigPrime() const
{
	if (this->num.size() > 3)
		return ((*this & Mask(3)) + (*this >> 96) * 0xffffffff).ModBigPrime();
	else
		return *this;
}

std::array<Integer, 32> Integer::InitExpTable(bool dir)
{
	std::array<Integer, 32> arr;
	Integer n;

	if (dir)
	{
		n = PrimitiveRoot;

		for (unsigned i = 0; i < 64; ++i)
			n = Square(n) % BigPrime;

		n = (n * InversePrimitiveRoot) % BigPrime;
	}
	else
	{
		n = InversePrimitiveRoot;

		for (unsigned i = 0; i < 64; ++i)
			n = Square(n) % BigPrime;

		n = (n * PrimitiveRoot) % BigPrime;
	}

	for (unsigned i = 0; i < 32; ++i)
		arr[31 - i] = n = Square(n) % BigPrime;

	return std::move(arr);
}

void Integer::FFT(std::vector<Integer> &coefficient)
{
	const unsigned size = coefficient.size();
	std::vector<Integer> temp(size);

	for (unsigned gap = size >> 1, len = 1; gap > 0; gap >>= 1, ++len)
	{
		const Integer g0 = Integer::ExpPrimitiveRoot[len];

		for (unsigned i = 0; i < gap; ++i)
		{
			unsigned pos1 = i;
			unsigned pos2 = i | (size >> 1);
			Integer g(1);

			for (unsigned j = i; j < size; j += (gap << 1))
			{
				Integer p = (g * coefficient[j + gap]).ModBigPrime();
				temp[pos1] = coefficient[j] + p;
				temp[pos2] = coefficient[j] - p;

				if (temp[pos2].sgn == -1)
					temp[pos2] += BigPrime;

				pos1 += gap;
				pos2 += gap;
				g = (g * g0).ModBigPrime();
			}
		}

		coefficient.swap(temp);
	}

	std::for_each(coefficient.begin(), coefficient.end(), [](Integer &x){x %= BigPrime;});
}

void Integer::FFT(std::vector<Integer> &coefficient1, std::vector<Integer> &coefficient2)
{
	const unsigned size = coefficient1.size();
	std::vector<Integer> temp1(size), temp2(size);

	for (unsigned gap = size >> 1, len = 1; gap > 0; gap >>= 1, ++len)
	{
		const Integer g0 = Integer::ExpPrimitiveRoot[len];

		for (unsigned i = 0; i < gap; ++i)
		{
			unsigned pos1 = i;
			unsigned pos2 = i | (size >> 1);
			Integer g(1);

			for (unsigned j = i; j < size; j += (gap << 1))
			{
				Integer p = (g * coefficient1[j + gap]).ModBigPrime();
				Integer q = (g * coefficient2[j + gap]).ModBigPrime();
				temp1[pos1] = coefficient1[j] + p;
				temp1[pos2] = coefficient1[j] - p;
				temp2[pos1] = coefficient2[j] + q;
				temp2[pos2] = coefficient2[j] - q;

				if (temp1[pos2].sgn == -1)
					temp1[pos2] += BigPrime;

				if (temp2[pos2].sgn == -1)
					temp2[pos2] += BigPrime;

				pos1 += gap;
				pos2 += gap;
				g = (g * g0).ModBigPrime();
			}
		}

		coefficient1.swap(temp1);
		coefficient2.swap(temp2);
	}

	std::for_each(coefficient1.begin(), coefficient1.end(), [](Integer &x){x %= BigPrime;});
	std::for_each(coefficient2.begin(), coefficient2.end(), [](Integer &x){x %= BigPrime;});
}

void Integer::iFFT(std::vector<Integer> &coefficient)
{
	const unsigned size = coefficient.size();
	std::vector<Integer> temp(size);

	for (unsigned gap = size >> 1, len = 1; gap > 0; gap >>= 1, ++len)
	{
		const Integer g0 = Integer::ExpInversePrimitiveRoot[len];

		for (unsigned i = 0; i < gap; ++i)
		{
			unsigned pos1 = i;
			unsigned pos2 = i | (size >> 1);
			Integer g(1);

			for (unsigned j = i; j < size; j += (gap << 1))
			{
				Integer p = (g * coefficient[j + gap]).ModBigPrime();
				temp[pos1] = coefficient[j] + p;
				temp[pos2] = coefficient[j] - p;

				if (temp[pos2].sgn == -1)
					temp[pos2] += BigPrime;

				pos1 += gap;
				pos2 += gap;
				g = (g * g0).ModBigPrime();
			}
		}

		coefficient.swap(temp);
	}

	std::for_each(coefficient.begin(), coefficient.end(), [](Integer &x){x %= BigPrime;});
}

Integer Integer::Random(const unsigned size)
{
	static std::mt19937 randgen(time(nullptr));
	static std::uniform_int_distribution<unsigned> uid;
	Integer num;
	num.sgn = 1;
	num.num.reserve(size);

	for (unsigned i = 0; i < size; ++i)
		num.num.push_back(uid(randgen));

	while (num.num.back() == 0)
		num.num.pop_back();

	return num;
}
